package LeetCode;

//
// Created by ✎﹏ℳ๓独赏☆独醉 on 2024/5/10.
//
//https://leetcode.cn/problems/search-in-rotated-sorted-array/description/
public class 搜索旋转排序数组 {
    public static void main(String[] args) {
        int[] nums = {1,3};
        int target = 0;
        System.out.println(search(nums,target));
    }
    public static int search(int[] nums, int target) {
        if (nums.length == 1)return nums[0] == target ? 0 : -1;
        int temp = -1;
        for (int i = 0; i < nums.length - 1; i++) {
            if(nums[i] > nums[i + 1]){
                temp = i;
                break;
            }
        }
        if(temp != -1){
            if(nums[0] <= target && target <= nums[temp]){
                int[] tempArr = new int[temp + 1];
                System.arraycopy(nums,0,tempArr,0,temp  + 1);
                return findTarget(0,tempArr.length,target,tempArr);
            }else if(nums[temp + 1] <= target && target <= nums[nums.length -1]){
                int[] tempArr = new int[nums.length - temp - 1];
                System.arraycopy(nums,temp + 1, tempArr,0,nums.length - temp - 1);
                int t = findTarget(0,tempArr.length-1,target,tempArr);
                if(t == -1){
                    return -1;
                }else {
                    return temp + 1 + findTarget(0,tempArr.length-1,target,tempArr);
                }
            }else {
                return  -1;
            }
        }else {
            return findTarget(0, nums.length-1,target,nums);
        }
    }

    private static int findTarget(int left, int right,int target,int[] nums) {
        while(left <= right){
            if(nums[(left + right)/2] > target)right--;
            if(nums[(left + right)/2] < target)left++;
            if(nums[(left + right)/2] == target)return (left + right)/2;
        }
        return -1;
    }
}
